Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo109 + 7.
The floor() function returns the integer part of the division.
Input: nums = [2,5,9] Output: 10 Explanation: floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0 floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1 floor(5 / 2) = 2 floor(9 / 2) = 4 floor(9 / 5) = 1 We calculate the floor of the division for every pair of indices in the array then sum them up.
Input: nums = [7,7,7,7,7,7,7] Output: 49
1 <= nums.length <= 1051 <= nums[i] <= 105
classSolution: defsumOfFlooredPairs(self, nums: List[int]) ->int: prevsum=0ret=0nums.sort() forjinrange(len(nums)): ifj>0andnums[j] ==nums[j-1]: ret= (ret+prevsum) %1000000007continuei=bisect.bisect(nums, nums[j] -1) prevsum=0forxinrange(1, nums[-1] //nums[j] +1): k=bisect.bisect(nums, nums[j] * (x+1) -1, lo=i) prevsum= (prevsum+x* (k-i)) %1000000007i=kret= (ret+prevsum) %1000000007returnret